package algo.A03_递归和算法复杂度;

import util.ArrayUtil;

public class T07_插入排序 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 1, 100);
        solution(arr, arr.length - 1);
    }

    /**
     * position是对下标为0-position的元素进行插入排序，因此position最大值为数组长度-1
     * @param arr
     * @param position
     */
    private static void solution(int[] arr, int position) {
        if (position == 0) {
            ArrayUtil.print(arr);
            return;
        }
        //对没有排过的元素进行插入排序
        solution(arr, position - 1);
        //将位置position的元素插入到前面的部分
        int x = arr[position];
        //记录插入该元素之前的最后一个元素下标
        int lastIndex = position - 1;
        //只要当前元素比最后一个小，就一直往后移动，给当前元素腾出位置
        while (lastIndex >= 0 && x < arr[lastIndex]) {
            arr[lastIndex + 1] = arr[lastIndex];
            //每移动一次最后一个元素下标要减1
            lastIndex--;
        }
        //以上循环执行完成后已经腾出了插入了位置
        arr[lastIndex + 1] = x;
    }
}
